A branch-and-price approach for a generalization of the HCSTP with multiple root nodes is discussed in \cite{GouveiaHCSTPMR}. We use their notation and base our solution on their model UPath\textsuperscript{D} with simplifications where possible.

\medskip

Let $S = V \setminus (T \cup \{0\})$ denote the set of Steiner nodes. Let $A = \{(i,j),(j,i): \{i,j\} \in E\}$ denote the set of arcs in the directed graph induced by $G$. Let $\mathcal{W}_t \subseteq 2^A$ denote the set of directed hop-constrained paths from $0$ to $t \in T$, i.e.\ $\forall p \in \mathcal{W}_t: l(p) \leq H$, where $l(p)$ denotes the length of the path $p$.

Our IMP contains the following variables:

\begin{itemize}
\item $\lambda_p^t \; \forall t \in T, \forall p \in \mathcal{W}_t$ denote the path variables, grouped by their end vertex. $\lambda_p^t$ is 1 if the solution contains the path $p$ from $0$ to $t$, and 0 otherwise.
\item $a_{ij} \; \forall (i,j) \in A$ denote the arc variables. $a_{ij}$ is 1 if $(i,j)$ is part of the solution, and 0 otherwise.
\item $y_v \; \forall v \in S$ denote the node variables of potential Steiner nodes. $y_v$ is 1 if $v$ is part of the solution, and 0 otherwise.
\end{itemize}

Our IMP is defined as follows:

\begin{align}
\min \quad \sum_{e=\{i,j\} \in E} c_e(a_{ij}+a_{ji}) & \label{eq:ex14obj} \\
\textrm{s.t.} \quad \sum_{p \in \mathcal{W}_t} \lambda_p^t & = 1 & \forall t \in T \label{eq:ex14reach} \\
\sum_{p \in \mathcal{W}_t: \, (i,j) \in p} \lambda_p^t & \leq a_{ij} & \forall t \in T, \forall (i,j) \in A \label{eq:ex14link} \\
\lambda_p^t & \geq 0 & \forall t \in T, \forall p \in \mathcal{W}_t \label{eq:ex14nonneg} \\
a_{ij} + a_{ji} & \leq y_i & \forall \{i,j\} \in E, i \in S \label{eq:ex14steiner} \\
\sum_{(i,j) \in A} a_{ij} & = |T| + \sum_{v \in S} y_v \label{eq:ex14tree} \\
a_{ij} & \in \{0,1\} & \forall (i,j) \in A \\
y_{v} & \in \{0,1\} & \forall v \in S
\end{align}

The objective function \eqref{eq:ex14obj} is to minimize the total edge cost in the solution. Constraints~\eqref{eq:ex14reach} ensure that exactly one path to each terminal node is chosen. Constraints~\eqref{eq:ex14link} link the path variables to the arc variables, such that the variable of each arc, that is contained in a chosen path, equals one. Constraints~\eqref{eq:ex14nonneg} ensure that path variables are non-negative. Constraints~\eqref{eq:ex14steiner} ensure that the variables of Steiner nodes with incident edges are set to one. Finally, constraint~\eqref{eq:ex14tree} ensures that the solution is acyclic.

While the arc variables and Steiner node variables are required to be either zero or one, further restrictions are not necessary for the path variables: Constraints~\eqref{eq:ex14reach} ensure that path variables are at most one and integrality follows from the integrality of arc variables, the linking between path and arc variables and constraint~\eqref{eq:ex14tree}.

\medskip

The pricing subproblem consists of choosing a new path variable $\lambda_p^t$ that will minimize the reduced cost function $\bar{c}_j = c_j - p^T \vc{A}_j$. For our IMP, $c_j$ is zero because the path variables do not appear in the objective function. Constraints~\eqref{eq:ex14reach} and~\eqref{eq:ex14link} are relevant for the pricing subproblem, and we denote the associated dual variables by $\mu_t$ and $\pi_{ij}^t$ respectively. Thus the objective is to choose $t \in T$ and $p \in \mathcal{W}_t$ in order to minimize $-\mu_t - \sum_{(i,j) \in p} \pi_{ij}^t$. Because constraints~\eqref{eq:ex14link} are inqualities, it follows that $\pi_{ij}^t \leq 0 \, \forall t \in T, \forall (i,j) \in A$.

This means that the pricing subproblem is equivalent to solving a hop-constrained path problem on each of the weighted directed graphs $G_1,\ldots,G_{|T|}$, where $G_t=(V,A,w_t)$ and $w_t: (i,j) \mapsto -\pi_{ij}^t$. Since the arc costs $-\pi_{ij}^t$ are non-negative, the problem can be solved on each graph with a modified version of Dijkstra's algorithm, that takes the hop limit into account. The result will be shortest path costs $s_t \, \forall t \in T$ for each of the graphs. The pricing subproblem now becomes: $t^* = \arg \min_t -\mu_t + s_t$. Let $p^*$ denote the shortest hop-constrained path that was found in $G_{t^*}$. The variable $\lambda_{p^*}^{t^*}$ minimizes the reduced costs and is added to the master problem. Solving the pricing subproblem is possible in $\mathcal{O}\left(|T|(|V| \log |V| + |E|)\right)$ which is polynomial in the size of the instance.

